﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>

using namespace std;


//给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
//
//树的 最大宽度 是所有层中最大的 宽度 。
//
//每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。
//将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
//
//题目数据保证答案将会在  32 位 带符号整数范围内
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution
{
public:
    int widthOfBinaryTree(TreeNode* root)
    {
        if (root == nullptr)
            return 0;
        vector<pair<TreeNode*, unsigned int>> q;//用数组模拟队列
        q.push_back({ root,1 });
        unsigned int ret = 0;
        while (q.size())
        {
            // 先更新这一层的宽度
            auto& [x1, y1] = q[0];
            auto& [x2, y2] = q.back();
            ret = max(ret, y2 - y1 + 1);
            // 用另外数组保存写一层的节点，保存节点和下标
            vector<pair<TreeNode*, unsigned int>> tmp;
            for (auto& [x, y] : q)
            {
                if (x->left) tmp.push_back({ x->left,2 * y });
                if (x->right) tmp.push_back({ x->right,2 * y + 1 });
            }

            q = tmp;
        }

        return ret;
    }
};


//给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。
//即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。


class Solution
{
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root)
    {
        // 进程层序遍历，记录每一层的元素的个数，然后进行插入其左右孩子(不为空)，自己用数组保存
        queue<TreeNode*> q;
        vector<vector<int>> ret;
        if (root == nullptr)
            return ret;
        q.push(root);
        int flag = 0;
        while (q.size())
        {
            int sz = q.size();
            vector<int> tmp;
            for (int i = 0; i < sz; i++)
            {
                auto t = q.front();
                tmp.push_back(t->val);
                if (t->left)
                    q.push(t->left);
                if (t->right)
                    q.push(t->right);
                q.pop();
            }
            if (flag % 2 == 1)
                reverse(tmp.begin(), tmp.end());
            ret.push_back(tmp);
            flag++;
        }

        return ret;
    }
};

/*给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）*/
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};


class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        // 进程层序遍历，记录每一层的元素的个数，然后进行插入其孩子(不为空)，自己用数组保存
        queue<Node*> q;
        vector<vector<int>> ret;
        if (root == nullptr)
            return ret;
        q.push(root);
        while (q.size())
        {
            int sz = q.size();
            vector<int> tmp;
            for (int i = 0; i < sz; i++)
            {
                auto t = q.front();
                tmp.push_back(t->val);
                // 遍历孩子数组，不为空就进行插入
                for (auto& child : t->children)
                    if (child)
                        q.push(child);
                q.pop();
            }
            ret.push_back(tmp);
        }

        return ret;
    }
};

//给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，
//只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。
class Solution
{
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped)
    {
        // 直让元素进栈，进栈的同时判断是否需要出栈。当所有元素模拟完毕之后，
        // 如果栈中还有元素，那么就是⼀个⾮法的序列。否则，就是⼀个合法的序列。
        stack<int> st;
        int i = 0, n = popped.size();
        for (auto x : pushed)
        {
            st.push(x);
            while (st.size() && st.top() == popped[i])
            {
                st.pop();
                i++;
            }
        }

        return st.empty();
    }
};


//给定一个经过编码的字符串，返回它解码后的字符串。
//
//编码规则为 : k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
//
//你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
//
//此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

//我们可以定义两个栈结构，⼀个⽤来保存解码前的重复次数 k （左括号前的数字），
//⼀个⽤来保存解码之前字符串的信息（左括号前的字符串信息）
class Solution
{
public:
    string decodeString(string s)
    {
        stack<int> num;
        stack<string> st;
        st.push("");
        int i = 0, n = s.size();
        while (i < n)
        {
            if (s[i] >= '0' && s[i] <= '9')
            {
                int cnt = 0;
                // 计算次数
                while (s[i] >= '0' && s[i] <= '9')
                {
                    cnt = cnt * 10 + (s[i] - '0');
                    i++;
                }
                // 加入数字栈
                num.push(cnt);
            }
            else if (s[i] == '[')
            {
                string str("");
                i++;
                // 加入字符串
                while (s[i] >= 'a' && s[i] <= 'z')
                {
                    str += s[i++];
                }
                st.push(str);
            }
            else if (s[i] == ']')
            {
                // 取出字符串增加n次
                int sz = num.top();
                num.pop();
                string tmp = st.top();
                st.pop();
                while (sz--)
                {
                    st.top() += tmp;
                }
                i++;// 跳过这个右括号
            }
            else
            {
                // 字符全部加入字符串栈顶
                string tmp;
                while (i < n && s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i++];
                }
                st.top() += tmp;
            }
        }
        return st.top();
    }
};


/*给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在[-231, 231 - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() */
class Solution
{
public:
    int calculate(string s)
    {
        // 当⼀个数前⾯是 '+' 号的时候，这⼀个数是否会被⽴即计算是「不确定」的，
        // 因此我们可以先压⼊栈中；
        // 当⼀个数前⾯是 '-' 号的时候，这⼀个数是否被⽴即计算也是「不确定」的，
        // 但是这个数已经和前⾯ 的 - 号绑定了，因此我们可以将这个数的相反数压⼊栈中；
        // 当⼀个数前⾯是 '*' 号的时候，这⼀个数可以⽴即与前⾯的⼀个数相乘，
        // 此时我们让将栈顶的元素乘上这个数；
        // 当⼀个数前⾯是 '/' 号的时候，这⼀个数也是可以⽴即被计算的，
        // 因此我们让栈顶元素除以这个数。
        // 当遍历完全部的表达式的时候，栈中剩余的「元素之和」就是最终结果
        stack<int> st;
        int i = 0, n = s.size();
        char op = '+';
        while (i < n)
        {
            if (s[i] == ' ')
                i++;
            else if (s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9')
                    tmp = tmp * 10 + (s[i++] - '0');
                if (op == '+')
                    st.push(tmp);
                else if (op == '-')
                    st.push(-tmp);
                else if (op == '*')
                    st.top() *= tmp;
                else
                    st.top() /= tmp;
            }
            else
                op = s[i++];
        }
        int ret = 0;
        while (!st.empty())
        {
            ret += st.top();
            st.pop();
        }

        return ret;
    }
};
int main()
{

	return 0;
}